#include <stdio.h>
#include <stdlib.h>
#include "uthash.h"
typedef struct {
    int key; // 哈希表的 key
    int value; // 哈希表的 value
    UT_hash_handle hh; // /* 使得结构体支持哈希表 */  
} HashEntry;

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    HashEntry* idx = NULL; // 创建一个空哈希表
    HashEntry* e;
    for (int j = 0; ; j++) { // 枚举 j
        // 在左边找 nums[i]，满足 nums[i]+nums[j]=target
        int t = target - nums[j];
        HASH_FIND_INT(idx, &t, e);
        if (e) { // 找到了
            int* ans = malloc(2 * sizeof(int)); // 分配返回结果的内存空间
            *returnSize = 2; // ans 的长度
            ans[0] = e->value; // 存储第一个数的下标
            ans[1] = j; // 存储第二个数的下标
            HASH_CLEAR(hh, idx); // 释放内存
            return ans; // 返回结果数组的指针
        }
        // 保存 nums[j] 和 j（作为 key 和 value）到哈希表中
        e = malloc(sizeof(HashEntry));
        e->key = nums[j];
        e->value = j;
        HASH_ADD_INT(idx, key, e);
    }
}

// 作者：灵茶山艾府
// 链接：https://leetcode.cn/problems/two-sum/description/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。